package com.gqb.tree;

import java.util.ArrayList;
import java.util.List;

public class BalancedBinaryTree {
	public static class Node {
		private int data;
		private String name;
		private Node leftNode;
		private Node rightNode;
		private Node parent;

		public Node(int data, Node parentNode) {
			super();
			this.data = data;
			this.parent = this.parent;
		}

		public Node(int data, String name) {
			super();
			this.data = data;
			this.name = name;
		}

		public Node(int data) {
			super();
			this.data = data;
		}

		public Node() {
		}

		public String getName() {
			return name;
		}

		public void setName(String name) {
			this.name = name;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public Node getLeftNode() {
			return leftNode;
		}

		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}

		public Node getRightNode() {
			return rightNode;
		}

		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}

		public Node getParent() {
			return parent;
		}

		public void setParent(Node parent) {
			this.parent = parent;
		}
	}
	private Node root;
	
	public void add(int data){
		Node addNode=new Node(data);
		if(root==null){
			root=addNode;
		}else{
			Node insertNode= getInsertNode(root,data);
			addNode.parent=insertNode;
			if(data>insertNode.getData()){
				insertNode.rightNode=addNode;
			}else {
				insertNode.leftNode=addNode;
			}
			System.out.println("插入节点后的深度"+getDepth(root, 1));
			Node imBalanceNode=getImbalanceNode(insertNode);
			if(imBalanceNode!=null){//表示节点失衡了
				String imBalanceType=getImBalanceType(imBalanceNode, addNode);
				rotation(imBalanceType, imBalanceNode);
				System.out.println("插入节点后的深度失去平衡，调整类型为"+imBalanceType+",调整后的深度"+getDepth(root, 1));
			}
		}
	}
	/***
	 * 删除节点
	 * @param data
	 */
	public void delete(int data){
		if(data==root.getData()){//删除根节点，用根节点的前驱节点来作为新的根节点,如果前驱节点没有就找后继节点作为根节点，都没有就删除
			if(null==findPrecursorNode(root)){//前驱节点不为null
				Node precursorNode=findPrecursorNode(root);
				if(precursorNode==precursorNode.parent.leftNode){
					precursorNode.parent.leftNode=null;
				}else{
					precursorNode.parent.rightNode=null;
				}
				precursorNode.leftNode=root.leftNode;
				precursorNode.rightNode=root.rightNode;
				root.leftNode.parent=precursorNode;
				root.rightNode.parent=precursorNode;
				root=precursorNode;
			}else{//前驱节点是null 就要查找后继节点
				if (null==findSuccessorNode(root)){
					//后继节点不为null
					Node successorNode=findSuccessorNode(root);
					if(successorNode==successorNode.parent.leftNode){
						successorNode.parent.leftNode=null;
					}else{
						successorNode.parent.rightNode=null;
					}
					successorNode.leftNode=root.leftNode;
					successorNode.rightNode=root.rightNode;
					root.leftNode.parent=successorNode;
					root.rightNode.parent=successorNode;
					root=successorNode;
				} 
				else{
					//前驱和后继都为null 直接删除根节点
					root=null;
				}
			}
		}else{//删除节点不是根节点
			Node deleteNode=findNode(root, data);
			if(null==deleteNode.leftNode&&null==deleteNode.rightNode){
				if(deleteNode.leftNode.data==data){
					deleteNode.parent.leftNode=null;
				}else{
					deleteNode.parent.rightNode=null;
				}
			}else{
				if(null!=findPrecursorNode(deleteNode)){//有前驱节点
					Node precursorNode=findPrecursorNode(deleteNode);
					//start 这里做的是，将前驱节点的儿子放到前驱节点的父亲上
					if(precursorNode==precursorNode.parent.leftNode){//前驱节点是做儿子的情况
						if(precursorNode.leftNode!=null)//切前驱节点的的左儿子不是null，这里一个可以确定的是，前驱节点和后继节点的右儿子一定是null
						{
							Node parentNode=precursorNode.parent;
							parentNode.leftNode=precursorNode.leftNode;
							precursorNode.leftNode.parent=parentNode;
						}
					}else {//前驱节点是右儿子的情况，且其做儿子不是空
						if(precursorNode.leftNode!=null){
							Node parenNode=precursorNode.parent;
							parenNode.rightNode=precursorNode.leftNode;
							precursorNode.leftNode.parent=parenNode;
						}
					}
					if(deleteNode==deleteNode.parent.leftNode){//删除节点是父节点的左儿子
						deleteNode.parent.leftNode=precursorNode;
					}else{//删除节点是父节点的右儿子
						deleteNode.parent.rightNode=precursorNode;
					}
					if(precursorNode!=deleteNode.leftNode&&precursorNode!=deleteNode.rightNode){
						precursorNode.leftNode=deleteNode.leftNode;
						precursorNode.rightNode=deleteNode.rightNode;
						deleteNode.leftNode.parent=precursorNode;
						deleteNode.rightNode.parent=precursorNode;
					}else{
						if(precursorNode==deleteNode.leftNode){
							precursorNode.rightNode=deleteNode.rightNode;
							if(deleteNode.rightNode!=null){
								deleteNode.rightNode.parent=precursorNode;
							}
						}else {
							precursorNode.leftNode=deleteNode.leftNode;
							deleteNode.leftNode.parent=precursorNode;
						}
					}
					precursorNode.parent=deleteNode.parent;
				}else  {
					if (null!=findSuccessorNode(deleteNode)){
						Node successorNode=findSuccessorNode(deleteNode);
						if(successorNode==successorNode.parent.leftNode){
							if(successorNode.leftNode!=null){//后继节点的做儿子不是null，前驱节点和后继节点的右儿子一定是null
								Node parentNode=successorNode.parent;
								parentNode.leftNode=successorNode.leftNode;
								successorNode.leftNode.parent=parentNode;
							}
						}else{//后继节点是右儿子的情况，且其做儿子不是空
							if(successorNode.leftNode!=null){
								Node parenNode=successorNode.parent;
								parenNode.rightNode=successorNode.leftNode;
								successorNode.leftNode.parent=parenNode;
							}
						}
						if(deleteNode==deleteNode.parent.leftNode){//删除节点是父节点的左儿子
							deleteNode.parent.leftNode=successorNode;
						}else{//删除节点是父节点的右儿子
							deleteNode.parent.rightNode=successorNode;
						}
						if(successorNode!=deleteNode.leftNode&&successorNode!=deleteNode.rightNode){
							successorNode.leftNode=deleteNode.leftNode;
							successorNode.rightNode=deleteNode.rightNode;
							deleteNode.leftNode.parent=successorNode;
							deleteNode.rightNode.parent=successorNode;

						}else{
							if(successorNode==deleteNode.rightNode){
								successorNode.parent=deleteNode.parent;
								if(deleteNode.leftNode!=null){
									deleteNode.leftNode.parent=successorNode;
								}
							}
						}
						successorNode.parent=deleteNode.parent;
					}else{
						if(deleteNode==deleteNode.parent.leftNode){
							deleteNode.parent.leftNode=null;
						}else {
							deleteNode.parent.rightNode=null;
						}
					}
				}
			}
			//TODO 这里有个删除时如何找到失去平衡的类型的问题
			Node imBalanceNode=getImbalanceNode(deleteNode);
			if(imBalanceNode!=null){//表示节点失衡了
				String imBalanceType=getImBalanceType(imBalanceNode, deleteNode);
				rotation(imBalanceType, imBalanceNode);
				System.out.println("删除节点后的深度失去平衡，调整类型为"+imBalanceType+",调整后的深度"+getDepth(root, 1));
			}
		}
	}
	
	/**
	 * 查找某个点的前驱节点
	 * @param node
	 * @return
	 */
	private Node findPrecursorNode(Node node){
		Node precursorNode=node.leftNode;
		if(null==precursorNode)
			return null;
		while (null!=precursorNode.leftNode) {
			precursorNode=precursorNode.leftNode;
		}
		return precursorNode;
	}
	/**
	 * 查找某个点的后继节点
	 * @param node
	 * @return
	 */
	private Node findSuccessorNode(Node node){
		Node successorNode=node.rightNode;
		if(null==successorNode)
			return null;
		while (null!=successorNode.rightNode) {
			successorNode=successorNode.rightNode;
		}
		return successorNode;
	}
	
	private Node findNode(Node rootNode,int data){
		if(rootNode.data==data){
			return rootNode;
		}
		if(rootNode.data>data){
			if(rootNode.leftNode!=null)
				return findNode(rootNode.leftNode, data);
			return null;
		}else{
			if(null!=rootNode.rightNode)
				return findNode(rootNode.rightNode, data);
			return null;
		}
		
		
	}
	private void rightRotation(Node rotationNode){
		Node sonOfRotationNode=rotationNode.leftNode;
		rotationNode.leftNode=sonOfRotationNode.rightNode;
		if(null!=sonOfRotationNode.rightNode){
			sonOfRotationNode.rightNode.parent=rotationNode;
		}
		sonOfRotationNode.parent=rotationNode.parent;
		if(null==rotationNode.parent){//rotationNode 是父节点，所以其父节点是null
			this.root=sonOfRotationNode;
		}else if (rotationNode==rotationNode.parent.leftNode) {
			rotationNode.parent.leftNode=sonOfRotationNode;
		}else{
			rotationNode.parent.rightNode=sonOfRotationNode;
		}
		sonOfRotationNode.rightNode=rotationNode;
		rotationNode.parent=sonOfRotationNode;
	}
	
	private void leftRotation(Node rotationNode){
		Node sonOfRotationNode=rotationNode.rightNode;
		rotationNode.rightNode=sonOfRotationNode.leftNode;
		if(null!=sonOfRotationNode.leftNode){//
			sonOfRotationNode.leftNode.parent=rotationNode;
		}
		sonOfRotationNode.parent=rotationNode.parent;
		if(null==rotationNode.parent){//rotationNode 是父节点，所以其父节点是null
			this.root=sonOfRotationNode;
		}else if(rotationNode==rotationNode.parent.leftNode) {
			rotationNode.parent.leftNode=sonOfRotationNode;
		}else{
			rotationNode.parent.rightNode=sonOfRotationNode;
		}
		sonOfRotationNode.leftNode=rotationNode;
		rotationNode.parent=sonOfRotationNode;
		
	}
	
	private void rotation(String imbalanceType,Node imbalanceNode){
		switch (imbalanceType) {
		case "RR":
			leftRotation(imbalanceNode);
			break;
		case "LL":
			rightRotation(imbalanceNode);
			break;
		case "RL":
			//对于RL型，现对失衡节点的右子节点进行右旋，然后再对失衡节点进行左旋
			rightRotation(imbalanceNode.rightNode);
			leftRotation(imbalanceNode);
			break;
		case "LR":
			//先对失衡节点的左孩子进行左旋，再对失衡节点进行右旋
			leftRotation(imbalanceNode.leftNode);
			rightRotation(imbalanceNode);
			break;
		default:
			break;
		}
	}
	
	private String  getImBalanceType(Node imBalanceNode,Node addNode){
		String type;
		if(addNode.getData()<imBalanceNode.getData()){
			if(addNode.getData()<imBalanceNode.getLeftNode().getData()){
				type="LL";
			}else {
				type="LR";
			}
		}else{
			if(addNode.getData()<imBalanceNode.getRightNode().getData()){
				type="RL";
			}else {
				type="RR";
			}
		}
		return type;
	}
	/**
	 * 查找第一个失衡节点
	 * @param node
	 * @return
	 */
	private Node getImbalanceNode(Node node){
		while(null!=node){
			int leftTreeDepth=getDepth(node.leftNode,1);
			int rightTreeDepth=getDepth(node.rightNode,1);
			if(leftTreeDepth-rightTreeDepth>1||leftTreeDepth-rightTreeDepth<-1){
				return node;
			}
			else{
				node=node.parent;
			}
		}
		return null;
	}
	/**
	 * 返回某个节点的深度
	 * @param node
	 * @param depth
	 * @return
	 */
	public int getDepth(Node node,int depth){
		int tempL=0,tempR=0,temp=0;
		if(null==node){
			return depth-1;
		}
		if(null!=node.leftNode){
			tempL=getDepth(node.leftNode, depth+1);
			if(tempL>temp){
				temp=tempL;
			}
		}
		if(null!=node.rightNode){
			tempR=getDepth(node.rightNode, depth+1);
			if(tempR>temp)
				temp=tempR;
		}
		return depth>temp?depth:temp;
	}
	/**
	 * 获取插入节点的位置
	 * @param node
	 * @param data
	 * @return
	 */
	private Node getInsertNode(Node node,int data){
		if(data>node.getData()){
			if(node.rightNode==null)
			{
				return node;
			}else{
				return getInsertNode(node.rightNode, data);
			}
		}else{
			if(node.leftNode==null){
				return node;
			}else{
				return getInsertNode(node.leftNode, data);
			}
		}
	}
	/**
	 * 中序遍历
	 * @param root
	 * @return
	 */
	public List<Node> middleTraversal(Node root){
		List<Node> list=new ArrayList<BalancedBinaryTree.Node>();
		if(null!=root.leftNode){
			list.addAll(middleTraversal(root.leftNode));
		}
		list.add(root);
		if(null!=root.rightNode){
			list.addAll(middleTraversal(root.rightNode));
		}
		return list;
	}
	
	
	public static void main(String[] args) {
		BalancedBinaryTree tree=new BalancedBinaryTree();
		tree.add(80);
		tree.add(60);
		tree.add(100);
		tree.add(90);
		tree.add(120);
		tree.add(94);
		tree.add(95);
		List<Node> nodeList=tree.middleTraversal(tree.root);
		for (Node node : nodeList) {
			System.out.print(node.getData()+"-");
		}
//		tree.add(94);
//		tree.add(93);
		List<Node> nodeLists=tree.middleTraversal(tree.root);
		
		tree.delete(94);
		/*for (Node node : nodeLists) {
			System.out.print(node.getData()+"-");
		}
		tree.add(130);
		tree.add(140);
		List<Node> nodeListss=tree.middleTraversal(tree.root);
		for (Node node : nodeListss) {
			System.out.print(node.getData()+"-");
		}
		tree.add(50);
		nodeListss=tree.middleTraversal(tree.root);
		for (Node node : nodeListss) {
			System.out.print(node.getData()+"-");
		}
		tree.add(70);
		tree.add(65);
		nodeListss=tree.middleTraversal(tree.root);
		for (Node node : nodeListss) {
			System.out.print(node.getData()+"-");
		}*/
	}
}
